Distributed cloud networking enables the deployment of network services in the form of interconnected virtual network functions instantiated over general purpose hardware at multiple cloud locations distributed across the network. The service distribution problem may be to find the placement of virtual functions and the routing of network flows that meet a given set of demands with minimum cost.